//给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现
//次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums1 = [1,2,2,1], nums2 = [2,2]
//输出：[2,2]
// 
//
// 示例 2: 
//
// 
//输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
//输出：[4,9] 
//
// 
//
// 提示： 
//
// 
// 1 <= nums1.length, nums2.length <= 1000 
// 0 <= nums1[i], nums2[i] <= 1000 
// 
//
// 
//
// 进阶： 
//
// 
// 如果给定的数组已经排好序呢？你将如何优化你的算法？ 
// 如果 nums1 的大小比 nums2 小，哪种方法更优？ 
// 如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？ 
// 
// Related Topics 数组 哈希表 双指针 二分查找 排序 👍 757 👎 0


import java.util.*;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution0350 {
    /**
     * [350]两个数组的交集 II: 用哈希表记录元素及元素出现的次数
     * <br>
     * 优化的点:
     * 1. 使用小数组映射哈希表, 可以占用最少的空间
     * 3. map.getOrDefault() 可以拿到默认值, 不用再去判断是否为空了
     * <p>
     * 时间复杂度: O(m+n)
     * <br>
     * 空间复杂度: O(min(n+m))
     */
    public int[] intersect(int[] nums1, int[] nums2) {
        // 交换大数组和小数组, 使用小数组映射哈希表, 可以占用最少的空间
        if (nums1.length > nums2.length) {
            return intersect(nums2, nums1);
        }

        Map<Integer, Integer> map = new HashMap<>(nums1.length);

        // 小数组, 映射后占用的额外空间少
        for (int num : nums1) {
            Integer count = map.getOrDefault(num, 0) + 1;
            map.put(num, count);
        }

        int[] container = new int[nums1.length];
        int index = 0;

        // 大数组
        for (int num : nums2) {
            Integer count = map.getOrDefault(num, 0);
            if (count > 0) {
                container[index++] = num;
                count--;
                if (count > 0) {
                    map.put(num, count);
                } else {
                    map.remove(num);
                }
            }
        }

        return Arrays.copyOfRange(container, 0, index);
    }
}
//leetcode submit region end(Prohibit modification and deletion)


class Test0350 {
    public static void main(String[] args) {
        int[] nums1 = {4, 9, 5};
        int[] nums2 = {9, 4, 9, 8, 4};

        // System.out.println(Arrays.toString(first(nums1, nums2)));
        // System.out.println(Arrays.toString(firstOptimization(nums1, nums2)));
        System.out.println(Arrays.toString(firstOptimization(nums1, nums2)));
    }

    /**
     * 用哈希表记录元素及元素出现的次数
     * <p>
     * 时间复杂度: O(n+m)
     * <br>
     * 空间复杂度: O(max(n+m))
     */
    public static int[] first(int[] nums1, int[] nums2) {
        // 交换大数组和小数组
        if (nums1.length < nums2.length) {
            return first(nums2, nums1);
        }

        Map<Integer, Integer> map = new HashMap<>(nums1.length);
        List<Integer> result = new ArrayList<>();

        // 大数组
        for (int num : nums1) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }

        // 小数组
        for (int num : nums2) {
            Integer count = map.get(num);
            if (count != null) {
                result.add(num);
                count--;
                if (count > 0) {
                    map.put(num, count);
                } else {
                    map.remove(num);
                }
            }
        }

        int length = result.size();
        int[] ret = new int[length];
        for (int i = 0; i < length; i++) {
            ret[i] = result.get(i);
        }
        return ret;
    }

    /**
     * 用哈希表记录元素及元素出现的次数, 根据题解进行优化
     * <br>
     * 优化的点:
     * 1. 使用小数组映射哈希表, 可以占用最少的空间
     * 2. 没必要创建一个 List, 直接创建一个数组(差不太多)
     * 3. map.getOrDefault() 可以拿到默认值, 不用再去判断是否为空了
     * 优化效果: 没啥太大提升
     * <p>
     * 时间复杂度: O(m+n)
     * <br>
     * 空间复杂度: O(min(n+m))
     */
    public static int[] firstOptimization(int[] nums1, int[] nums2) {
        // 交换大数组和小数组, 使用小数组映射哈希表, 可以占用最少的空间
        if (nums1.length > nums2.length) {
            return first(nums2, nums1);
        }

        Map<Integer, Integer> map = new HashMap<>(nums1.length);

        // 小数组, 映射后占用的额外空间少
        for (int num : nums1) {
            Integer count = map.getOrDefault(num, 0) + 1;
            map.put(num, count);
        }

        int[] container = new int[nums1.length];
        int index = 0;

        // 大数组
        for (int num : nums2) {
            Integer count = map.getOrDefault(num, 0);
            if (count > 0) {
                container[index++] = num;
                count--;
                if (count > 0) {
                    map.put(num, count);
                } else {
                    map.remove(num);
                }
            }
        }

        return Arrays.copyOfRange(container, 0, index);
    }


    /**
     * 将两个数组排序, 使用双指针进行筛选
     * <p>
     * 时间复杂度: O(m * log m + n * log n)
     * <br>
     * 空间复杂度: O(min(m,n))
     */
    public static int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1); // m * log m
        Arrays.sort(nums2); // n * log n

        int[] container = new int[Math.max(nums1.length, nums2.length)];
        int index = 0;

        int p1 = 0;
        int p2 = 0;
        while (p1 <= nums1.length && p2 <= nums2.length) {
            if (nums1[p1] < nums2[p2]) {
                p1++;
            } else if (nums1[p1] > nums2[p2]) {
                p2++;
            } else {
                container[index++] = nums1[p1];
                p1++; // m
                p2++; // n
            }
        }
        return Arrays.copyOfRange(container, 0, index); // index
    }

    /*
     * 如果 2nums 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中。
     * 那么就无法高效地对 2nums 进行排序，因此推荐使用哈希表而不是排序+双指针。
     * 在哈希表法中，2nums 只关系到查询操作，因此每次读取 2nums 中的一部分数据，并进行处理即可。
     * <p>
     * 如果内存十分小，不足以将数组全部载入内存，那么必然也不能使用哈希这类费空间的算法，
     * 只能选用空间复杂度最小的算法，即排序+双指针(外排|归并排序+双指针)。
     * 但是排序+双指针需要改造，一般说排序算法都是针对于内部排序，一旦涉及到跟磁盘打交道（外部排序），则需要特殊的考虑。
     * 归并排序是天然适合外部排序的算法，可以将分割后的子数组写到单个文件中，归并时将小文件合并为更大的文件。
     * 当两个数组均排序完成生成两个大文件后，即可使用双指针遍历两个文件，如此可以使空间复杂度最低。
     * 关于外部排序与JOIN，强烈推荐大家看一下 数据库内核杂谈（六）：表的 JOIN（连接）这一系列数据库相关的文章。
     */
}
